#include <iostream>
#include <vector>
#include <cmath>
#include <limits>
#include <algorithm>
#include <memory>
#include <thread>
#include <queue>
#include <functional> // 用于std::cref/std::ref
#include <numeric>    // 用于线程安全的索引分配

using namespace std;

// 飞行线结构体
struct FlightLine
{
    int id;
    double x1, y1, x2, y2;

    pair<pair<double, double>, pair<double, double>> getBoundingBox() const
    {
        return {{min(x1, x2), min(y1, y2)}, {max(x1, x2), max(y1, y2)}};
    }
};

// 查询点结构体
struct QueryPoint
{
    double x, y;
};

// KD树节点
struct KDNode : public enable_shared_from_this<KDNode>
{
    FlightLine line;
    shared_ptr<KDNode> left, right;
    weak_ptr<KDNode> parent;
    int axis;
    double splitValue;
    pair<pair<double, double>, pair<double, double>> bbox;

    KDNode(const FlightLine &ln, int ax, double sv)
        : line(ln), axis(ax), splitValue(sv), bbox(ln.getBoundingBox()) {}

    void updateBoundingBox()
    {
        bbox = line.getBoundingBox();
        if (left)
            mergeBBox(left->bbox);
        if (right)
            mergeBBox(right->bbox);
        if (auto p = parent.lock())
            p->updateBoundingBox();
    }

    void mergeBBox(const pair<pair<double, double>, pair<double, double>> &b)
    {
        bbox.first.first = min(bbox.first.first, b.first.first);
        bbox.first.second = min(bbox.first.second, b.first.second);
        bbox.second.first = max(bbox.second.first, b.second.first);
        bbox.second.second = max(bbox.second.second, b.second.second);
    }

    void insert(const FlightLine &newLine, int depth = 0)
    {
        int currentAxis = depth % 2;
        double newMid = currentAxis == 0 ? (newLine.x1 + newLine.x2) / 2 : (newLine.y1 + newLine.y2) / 2;

        if (newMid < splitValue)
        {
            if (!left)
            {
                left = make_shared<KDNode>(newLine, currentAxis, newMid);
                left->parent = shared_from_this();
                updateBoundingBox();
            }
            else
                left->insert(newLine, depth + 1);
        }
        else
        {
            if (!right)
            {
                right = make_shared<KDNode>(newLine, currentAxis, newMid);
                right->parent = shared_from_this();
                updateBoundingBox();
            }
            else
                right->insert(newLine, depth + 1);
        }
    }

    // 删除时传入root引用以便更新根节点
    bool remove(int targetId, shared_ptr<KDNode> &root)
    {
        if (line.id == targetId)
        {
            // 叶子节点
            if (!left && !right)
            {
                if (!parent.lock())
                    root = nullptr; // 根节点置空
                else
                {
                    auto p = parent.lock();
                    (p->left == shared_from_this()) ? p->left = nullptr : p->right = nullptr;
                    p->updateBoundingBox();
                }
                return true;
            }
            // 只有左子树
            else if (left && !right)
            {
                if (!parent.lock())
                    root = left; // 根节点替换为左子树
                else
                {
                    auto p = parent.lock();
                    p->replaceChild(shared_from_this(), left);
                    left->parent = p;
                }
                return true;
            }
            // 只有右子树
            else if (!left && right)
            {
                if (!parent.lock())
                    root = right; // 根节点替换为右子树
                else
                {
                    auto p = parent.lock();
                    p->replaceChild(shared_from_this(), right);
                    right->parent = p;
                }
                return true;
            }
            // 两个子树都存在，找右子树最小节点替换
            else
            {
                auto minNode = findMinNode(right, axis);
                line = minNode->line;
                return right->remove(minNode->line.id, root);
            }
        }
        bool removed = false;
        if (left)
            removed = left->remove(targetId, root);
        if (!removed && right)
            removed = right->remove(targetId, root);
        if (removed)
            updateBoundingBox();
        return removed;
    }

    // 查找最小节点
    shared_ptr<KDNode> findMinNode(shared_ptr<KDNode> node, int axis)
    {
        while (node->left)
            node = node->left;
        return node;
    }

    // 替换子节点
    void replaceChild(shared_ptr<KDNode> oldChild, shared_ptr<KDNode> newChild)
    {
        if (left == oldChild)
            left = newChild;
        else if (right == oldChild)
            right = newChild;
        if (newChild)
            newChild->parent = shared_from_this();
        updateBoundingBox();
    }
};

// 构建KD树
shared_ptr<KDNode> buildKDTree(vector<FlightLine> &lines, int depth = 0)
{
    if (lines.empty())
        return nullptr;
    int axis = depth % 2;
    nth_element(lines.begin(), lines.begin() + lines.size() / 2, lines.end(),
                [axis](const FlightLine &a, const FlightLine &b)
                {
                    double av = axis == 0 ? (a.x1 + a.x2) / 2 : (a.y1 + a.y2) / 2;
                    double bv = axis == 0 ? (b.x1 + b.x2) / 2 : (b.y1 + b.y2) / 2;
                    return av < bv;
                });
    auto node = make_shared<KDNode>(lines[lines.size() / 2], axis,
                                    axis == 0 ? (lines[lines.size() / 2].x1 + lines[lines.size() / 2].x2) / 2 : (lines[lines.size() / 2].y1 + lines[lines.size() / 2].y2) / 2);
    vector<FlightLine> leftLines(lines.begin(), lines.begin() + lines.size() / 2);
    vector<FlightLine> rightLines(lines.begin() + lines.size() / 2 + 1, lines.end());
    node->left = buildKDTree(leftLines, depth + 1);
    node->right = buildKDTree(rightLines, depth + 1);
    if (node->left)
        node->left->parent = node;
    if (node->right)
        node->right->parent = node;
    node->updateBoundingBox();
    return node;
}

// 计算点到线段距离平方
double pointToLineSq(const QueryPoint &p, const FlightLine &line)
{
    double x1 = line.x1, y1 = line.y1, x2 = line.x2, y2 = line.y2;
    double dx = x2 - x1, dy = y2 - y1;
    if (dx == 0 && dy == 0)
        return (p.x - x1) * (p.x - x1) + (p.y - y1) * (p.y - y1);
    double t = max(0.0, min(1.0, ((p.x - x1) * dx + (p.y - y1) * dy) / (dx * dx + dy * dy)));
    double projX = x1 + t * dx, projY = y1 + t * dy;
    return (p.x - projX) * (p.x - projX) + (p.y - projY) * (p.y - projY);
}

// 计算点到包围盒最小距离平方
double pointToBBoxSq(const QueryPoint &p, const pair<pair<double, double>, pair<double, double>> &bbox)
{
    double dx = max({bbox.first.first - p.x, 0.0, p.x - bbox.second.first});
    double dy = max({bbox.first.second - p.y, 0.0, p.y - bbox.second.second});
    return dx * dx + dy * dy;
}

// 搜索最近节点
void nearestSearch(shared_ptr<KDNode> node, const QueryPoint &p,
                   double &minSq, int &nearestId)
{
    if (!node)
        return;
    double bboxDist = pointToBBoxSq(p, node->bbox);
    if (bboxDist > minSq)
        return;

    double currDist = pointToLineSq(p, node->line);
    if (currDist < minSq || (currDist == minSq && node->line.id < nearestId))
    {
        minSq = currDist;
        nearestId = node->line.id;
    }

    bool goLeft = (node->axis == 0 ? p.x : p.y) < node->splitValue;
    if (goLeft)
    {
        nearestSearch(node->left, p, minSq, nearestId);
        if ((node->axis == 0 ? p.x - sqrt(minSq) : p.y - sqrt(minSq)) <= node->splitValue)
            nearestSearch(node->right, p, minSq, nearestId);
    }
    else
    {
        nearestSearch(node->right, p, minSq, nearestId);
        if ((node->axis == 0 ? p.x + sqrt(minSq) : p.y + sqrt(minSq)) >= node->splitValue)
            nearestSearch(node->left, p, minSq, nearestId);
    }
}

// 并行搜索辅助函数
void parallelSearch(
    shared_ptr<KDNode> root,
    const vector<QueryPoint> &queries,
    vector<int> &results,
    vector<size_t> &indices)
{
    for (size_t i = 0; i < indices.size(); ++i)
    {
        size_t queryIdx = indices[i];
        double minSq = numeric_limits<double>::max();
        int nearestId = -1;
        nearestSearch(root, queries[queryIdx], minSq, nearestId);
        results[queryIdx] = nearestId;
    }
}

// 并行查询接口
vector<int> findNearestFlightLineParallel(
    const shared_ptr<KDNode> &root,
    const vector<QueryPoint> &queryPoints)
{
    if (!root)
        return vector<int>(queryPoints.size(), -1);

    const size_t numQueries = queryPoints.size();
    vector<int> results(numQueries, -1);

    // 小数据集单线程处理
    if (numQueries < 200)
    {
        for (size_t i = 0; i < numQueries; ++i)
        {
            double minSq = numeric_limits<double>::max();
            nearestSearch(root, queryPoints[i], minSq, results[i]);
        }
        return results;
    }

    // 获取线程数并分配任务
    const size_t numThreads = thread::hardware_concurrency();
    vector<thread> threads;
    vector<vector<size_t>> threadIndices(numThreads);

    // 轮询分配索引，确保负载均衡
    for (size_t i = 0; i < numQueries; ++i)
    {
        threadIndices[i % numThreads].push_back(i);
    }

    // 启动线程
    for (size_t t = 0; t < numThreads; ++t)
    {
        threads.emplace_back(parallelSearch, root,
                             cref(queryPoints), ref(results),
                             ref(threadIndices[t]));
    }

    // 等待所有线程完成
    for (auto &thread : threads)
    {
        thread.join();
    }

    return results;
}

int main()
{
    int numTestCases;
    cout << "请输入测试用例的数量: ";
    cin >> numTestCases;

    for (int t = 1; t <= numTestCases; ++t)
    {
        cout << "\n=== 测试用例 " << t << " ===" << endl;
        int numLines;
        cout << "请输入飞行线的数量: ";
        cin >> numLines;

        vector<FlightLine> lines(numLines);
        int nextId = 1;
        for (int i = 0; i < numLines; ++i)
        {
            cout << "请输入飞行线 " << i + 1 << " 的坐标 (x1 y1 x2 y2): ";
            cin >> lines[i].x1 >> lines[i].y1 >> lines[i].x2 >> lines[i].y2;
            lines[i].id = nextId++;
        }

        shared_ptr<KDNode> root = buildKDTree(lines);
        int numQueries;
        cout << "请输入查询点的数量: ";
        cin >> numQueries;
        vector<QueryPoint> queries(numQueries);
        for (int i = 0; i < numQueries; ++i)
        {
            cout << "请输入查询点 " << i + 1 << " 的坐标 (x y): ";
            cin >> queries[i].x >> queries[i].y;
        }

        // 使用并行查询
        auto results = findNearestFlightLineParallel(root, queries);

        cout << "\n测试用例结果:" << endl;
        for (size_t i = 0; i < results.size(); ++i)
            cout << "查询点 " << i + 1 << " 最近ID: " << results[i] << endl;

        char choice;
        do
        {
            cout << "\n是否更新飞行线？(y/n): ";
            cin >> choice;
            if (choice != 'y')
                break;

            int op;
            cout << "选择操作 (1-添加, 2-删除): ";
            cin >> op;
            if (op == 1)
            {
                FlightLine newLine;
                cout << "输入新飞行线坐标 (x1 y1 x2 y2): ";
                cin >> newLine.x1 >> newLine.y1 >> newLine.x2 >> newLine.y2;
                newLine.id = nextId++;
                if (root)
                    root->insert(newLine);
                else
                    root = make_shared<KDNode>(newLine, 0, (newLine.x1 + newLine.x2) / 2);
                cout << "已添加 ID: " << newLine.id << endl;
            }
            else if (op == 2)
            {
                int delId;
                cout << "输入要删除的ID: ";
                cin >> delId;
                if (root)
                {
                    bool removed = root->remove(delId, root);
                    if (removed)
                    {
                        cout << "成功删除 ID: " << delId << endl;
                        if (!root)
                            cout << "树已为空" << endl;
                    }
                    else
                    {
                        cout << "未找到 ID: " << delId << endl;
                    }
                }
                else
                {
                    cout << "树为空，无法删除" << endl;
                }
            }

            // 重新查询（使用并行接口）
            results = findNearestFlightLineParallel(root, queries);
            cout << "\n更新后查询结果:" << endl;
            for (size_t i = 0; i < results.size(); ++i)
            {
                cout << "查询点 " << i + 1 << " 最近ID: "
                     << (results[i] == -1 ? "无（飞行线为0）" : to_string(results[i])) << endl;
            }
        } while (choice == 'y');
    }

    return 0;
}